自下而上分析法

使用归约法

一共有三种归约法

  • 简单优先分析法
  • 算符优先分析法
  • LR分析法

思想

  • 自下而上的语法分析过程是一个最左归约的过程，从输入串开始，朝着文法的开始符号进行归约，直到到达文法的开始符号为止的过程。
  • 注意:输入串在这里是指从词法分析器送来的单词符号组成的二元式的有限序列。、
  • 自下而上分析法使用下推自动机

下推自动机PDA

工作方式

  • 自左至右把输入串的符号一个一个移进栈，在移进过程中不断查看栈顶符号串，一旦形成某个句型的句柄时，就将此句柄用相应的产生式左部替换（归约）

  • 若再形成句柄，就继续替换，直到栈顶不再形成句柄为止。

  • 然后继续移进符号，重复上面的过程直到栈顶只剩下文法的开始符号，输入串读完为止，这样就可以认为识别了一个句子。

image-20220602160231219

注:

  • 1）初态时栈内仅有栈底符“#”，读头指在最左边的单词符号上。

语法分析程序执行的动作:

  • a）移进：读入一个单词并压入栈内，读头后移;
  • b) 归约：检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号;
  • c) 识别成功：移进一归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束符“#”
  • d) 识别失败

举例

image-20220602160717705

结果

image-20220602161150416

根据右边的语法树，很容易知道哪里可以归约，但怎么让计算机知道呢？？？？

下面的关键就是“如何找到句柄”

简单优先分析法

基本思想

  • 在句型中，句柄内各相邻符号之间具有相同的优先级。相同的优先级用“=”。
  • 由于句柄要先归约，所以规定句柄两端符号的优先级要比位于句柄之外的相邻符号的优先级高。
  • 优先级低于表示为"<".优先级高于表示">"
  • "#"的优先级最小，小于任何符号，遇到#时，将所有栈内元素出栈，进行归约

比如：S->aBe,B->bc。现在有abce，使用上面的优先级可以得出：a<b=c>e

在入栈时，：

栈底->栈顶 优先级比较(标红是要入栈)
#a a<b b入栈
#ab c=b c入栈
#abc e<c e不入栈，并弹出所有大于e的栈顶(依次弹出c,b)，归约产生B，B再入栈
#aB e=B e入栈
#aBe #<e #不入栈，并弹出所有大于#的栈顶（依次弹出e、B、a）归约成S，S再入栈
#S

使用条件

简单优先分析法，必须使用简单优先文法

定义:

  • 一个文法G，如果它不含ε产生式，也不含任何右部相同的不同产生式(不能同时有A->bc并且B->bc的)
  • 它的任何符号对(X,Y)->XY是非终结符或终结符，或者没有关系，或者存在优先级相同或低于、高于等关系之一，则这是一个简单优先文法。

简单优先级定义

  1. X=Y当且仅当G中含有形如 P→…XY
  2. X<Y当且仅当G中含有形如 P→…XQ…的产生式，其中Q→Y… Y先归约变成Q，Q再和X归约
  3. X>Y当且仅当Y为文法G的终结符，G中有形如P->……QR……，且Q->……X, Y属于Frist® Q的最后一个符号是X，R的第一个符号是Y

优先级判断的举例

  • S->aBc、B->b 这里的a<b(上面第二条),b>c(上面第三条)

算符优先分析

定义

  • 是仿效四则运算的计算过程而构造的一种语法分析方法，规定了算符的优先级
  • 不考虑非终结符的关系，主要考虑终结符的关系，如i+i-i*(i+i)

特点

  • 简单直观，特别方便于表达式分析，易于手工实现,是自下而上的归约过程，但未必按照句柄归约。3、算符优先分析法的关键:
  • 规定算符（终结符）的优先级及结合性质。

举例

规定了优先级，运算量i 大于 乘法&除法 大于 加法&减法

image-20220602204226287

直观算符分析法

和数据结构中，根据序列计算式子结果

  • 1)使用两个工作栈:一个算符栈(OPTR）存放运算符和括号;一个算量栈（ OPND)用于存放操作数和运算结果;
  • OPTR栈的栈顶符号用0表示,OPND栈的栈顶符号用π表示

在从左向右描述过程中，数据进入算量栈;当遇到符号，判断读头符号和栈顶符号的关系。

  • 如果读头符号小于等于栈顶符号，需要弹出栈顶符号和两个数据，做归约后，将归约结果放到数据栈。
  • 如果读头符号大于栈顶符号，则直接添加到符号栈中。
  • 如果是“（”，直接添加到符号栈
  • 如果是“）”，则从符号栈弹出一个符号并弹出两个数据，做归约后添加到数据栈。直到弹出“（”左括号
  • 如果读头已经到底，弹出符号栈一个，并依次弹出两个数据，归约后添加到数据栈……直到符号栈空掉

算符优先级定义

a与b的四种关系。另外，算符优先分析，不允许连续的两个非终结符出现，所以不会有P->……RQ……的情况

  • a=b 当且仅当G中含有形如 P- > …ab…产生式，或者P->..aQb.…产生式; ab同时归约
  • a<b 当且仅当G中含有形如 P- > …aR…的产生式，其中R-+->b…或R-+->Qb…;(R经过多步推出b)；说明R是由b归约得来的，所以b实际上先被归约，a后被归约，如下图。
  • a>b 当且仅当G中含有形如 P- >…Rb…产生式，其中R-+->……a,或R-+->……aQ. 说明R是由a归约得来的，所以a实际上先被归约，b后被归约
  • a和b无关系

Ai由B1到Bm归约而来

注意

  • 如果a=b ,b=c 不能推出a=c，等号只是表示优先级相同，但a和c可以表示没有任何关系，说明a和c不会连在一起
  • 比如：P->aAbBcCe,只能推出a=b,b=c,c=e

首终结符集和尾终结符集

求非终结符P的首终结符集&尾终结符集

vt表示终结符

首终结符集Firstvt§

首终结符集定义

构造Firstvt算法

方法1

image-20220603162751537
  • 由一步推导或多步推导

方法2

image-20220603162909986

  • 使用堆栈是为了考虑多步推导

image-20220603163041823

举例

  • S->aB,B->Cd,C->c
  • FirstVt(S)={a}
  • FirstVt(B)={d}+{c}
  • FirstVt©={c}
栈底->栈顶 操作
(S,a)
(B,d)
(C,c) 1、弹出C,c 有B->C的产生式，并且c不在FirstVT(B),F[B,c]为真，(B,c)入栈
栈底->栈顶 操作
(S,a) 3、弹出S,a 无X->S
(B,d) 2、弹出B,d 无X->B
(B,c) 1、弹出B,c 无X->B的产生式

image-20220603164436622

尾终结符集Lastvt§

尾终结符集定义

  • 有了这两个集合后，就可以通过检查每个产生式的每个候选式，确定满足关系<和>的所有终结符序偶。

算法

image-20220603164328245

举例

image-20220603164515193

判断归约顺序

判断归约顺序

题目

image-20220602223423339
  • FirstVt(S)={a},LastVt(S)={e}
  • FirstVt(A)={b},LastVt(A)={b}
  • FirstVt(B)={d},LastVt(B)={d}
a b c d e
a < =
b > >
c < =
d >
e

  • S->aAcBe，同优先级a=c,c=e 没有a=e

  • S->aA中，因为FirstVt(A)=b，所以 a<b ; 根据上面第一条

  • S->Ac中，因为FirstVt(A)=b，所以 b>c ; 根据上面第二条

  • S->cB中，FirstVt(B)=d，c<d 根据上面第一条

  • S->Be中，FirstVt(B)=d，d>e 根据上面第二条

  • A->Ab中，因为FirstVt(A)=b，所以b>b 根据上面第二条

题目2

image-20220603171405832

先求FirstVT

  • S->if Eb then E…… 满足P->a形式 FirstVt(S)={if}
  • E->E+T|T 满足P->Qa形式和P->Q FirstVt(E)={+} U FirstVt(T)={+,*,i}
  • T->T*F|F 满足P->Qa形式和P->Q FirstVt(T)={*} U FirstVt(F)={*,i}
  • F->i 满足P->a形式 FirstVt(F)={i}

再求LastVt

  • S->……else E 满足P->aQ形式 LastVt(S)={else} U LastVt(E)={else,+,*,i}
  • E->E+T|T 满足P->aQ形式和P->Q LastVt(E)={+} U LastVt(T)={+,*,i}
  • T->T*F|F 满足P->aQ形式和P->Q LastVt(T)={*} U LastVt(F)={*,i}
  • F->i 满足P->a形式 LastVt(F)={i}

求出FirstVT和LAstVt后，就方便写出算符优先表

算符优先表

填写表格时，先按行，再按列，按每个方法，两个两个的结合着看，如下过程：

先看S->if Eb then E else E

  • if和then是相同归约 所以if=then
  • if Eb属于 图【判断归约顺序】中第一个关系，又因为FirstVt(Eb)={b}，所以if<b
  • Eb then 属于第二个关系，FirstVt(Eb)={b}，所以b>then
  • then 和E 属于第一个关系，又因为FirstVt(E)={+,*,i}，所以then<{+,*,i}
  • then 和else 是相同归约，所以then=else
  • E 和 else 属于第二个关系，LastVt(E)={+,*,i}，所以+>else,*>else,i>else
  • else 和E 属于第一个关系，同then一样，else<{+,*,i}
  • else 因为是最后一个终结符，所以else>#

再看E->E+T|T

  • E 和 + 属于第二个关系，LastVt(E)={+,*,i}，所以+>+,*>+,i>+
  • +和T属于 第一个关系 FirstVt(T)={*,i},所以+<*,+<i
  • +因为是最后一个终结符，所以+>#

再看T->T*F|F

  • T和* 属于第二个关系 LastVt(T)={*,i} ,所以*>*,i>*
  • *和F 属于第一个关系 FirstVt(F)={i} ,所以*<i
  • *因为是最后一个终结符，所以*>#

再看F->i

  • i 因为是最后一个终结符，所以i>#

没了……

规范归约过程

image-20220603223807352

非规范分析

  • 终结符之间的优先关系，在算符优先分析中，仅研究考虑非终结符之间的优先关系，但句柄是由终结符和非终结符一起构成的，所以算符优先分相对来说是非规范的分析

和上面一样的题目，但算符归约方法如下：

image-20220603224051463

算符优先分析

  • 在算符优先分析中，可归约的短语不再称为句柄，而称为最左素短语。素短语是指这样一个短语，至少含有一个终结符，且除它自
    身外不再包含其他素短语，最左边的素短语称为最左素短语。

举例

image-20220603224614628

结果

最左素短语至少要有个终结符

image-20220603224624584

最左素短语的判断

image-20220603224734074

通用算符归约

根据上面的表格，不断将输入串入栈。终结符b/i大于其它符号

image-20220603230617970

序号 栈低->栈顶 读头 操作
0 # < if b then i else i # # < if if入栈
1 #if < b then i else i # if < b b入栈
2 #if b > then i else i # then < b,将b归约
3 #if N = then i else i # if = then(不是用N比较),then入栈
4 #if N then < i else i # then < i,i入栈
5 #if N then i > else i # i > else ,将i归约
6 #if N then N = else i # then = else,else 入栈
7 #if N then N else < i # else <i ,i入栈
8 #if N then N else i > # i > # ,将i归约
9 #if N then N else N > # 因为左边#<if 右边#<N所以将整个进行归约
10 #N # 归约成功

课后答案

https://wenku.baidu.com/view/afdafdd333d4b14e85246856.html